#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1005;
int deg[N];
int n,m;
int a,b;
int p[N];
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
void join(int x,int y){
    int fa=find(x);
    int fb=find(y);
    if(fa!=fb){
        p[fa]=fb;
    }
}

int main(void){
    while(~scanf("%d",&n)){
        if(n==0){
            break;
        }
        for(int i=1;i<=n;i++){
            p[i]=i;
        }
        memset(deg,0,sizeof(deg));
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&a,&b);
            deg[a]++;
            deg[b]++;
            join(a,b);
        }
        bool flag=true;
        int pa=find(1);
        for(int i=1;i<=n;i++){
            if(deg[i]%2 || find(i)!=pa){
                flag=false;
                break;
            }
        }
        printf("%d\n",flag);
    }
    return 0;
}